OT kombinacni pocet
Otázka od: Pavel Zichovsky
15. 4. 2004 11:15
Dobry den,
neni to sice primo o programovani, ale potrebuju to pro program v Delphi.
Trapim se uz nejakou dobu s timto problemem:
Jako rychlou kontrolu splnitelnosti vstupnich podminek pro jeden program v
Delphi
(rozlosovani turnaje) potrebuju spocitat pocet k-tic (bez ohledu na poradi,
k>2) z n-
prvkove mnoziny (n>k) za nasledujici omezujici podminky:
Libovolne dva prvky z mnoziny N muzou byt spolu maximalne v jedne k-tici.
Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny (n=12), a jedna
ctverice je (1,2,3,4), pak uz nesmi byt ctverice, kde by se vyskytovala
libovolna
dvojice z teto ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
Nedari se mi vymyslet postup, jak spocitat pocet platnych k-tic.
Dokazu spocitat pocet vsech moznych k-tic (jako kombinace k z n) ale uz nevim,
jak
spocitat pocet "neplatnych" k-tic (s "opakujicimi se" dvojicemi).
Nenasel by se nejaky matematik, ktery by mi s tim pomohl?
Mohl bych si sice programove udelat vypis vsech moznych k-tic a pak postupne
"vyskrtavat" neplatne, ale se zvysujicim se poctem n a k by to trvalo hrozne
dlouho,
takze kdyby to slo spocitat "vzoreckem", bylo by to jednodussi.
Diky za vsechny napady
S pozdravem
Pavel Zichovsky (zichovsky@trul.cz)
Odpovedá: Fitz Ladislav
15. 4. 2004 11:35
no nejsem matematik, ale mozna by to slo takhle matice booleanu n krat n a
pri pouzeti nejake kombiace treba (1,2,3,4) si zapsat do matice ze pole
[1,2][1,3][1,4][2,1][2,3][2,4][3,1][3,2][3,4][4,1][4,2][4,3] jiz byla
pouzita a pri sestavovani nove si toto testovat akorat by to mohlo byt
narocne na pamet a pak bych asi sel pres nastavovani bitu
Odpovedá: Pavel Zichovsky
15. 4. 2004 11:56
Zdravim,
On 15 Apr 2004 at 12:13, Fitz Ladislav wrote:
> pri pouzeti nejake kombiace treba (1,2,3,4) si zapsat do matice ze pole
> [1,2][1,3][1,4][2,1][2,3][2,4][3,1][3,2][3,4][4,1][4,2][4,3] jiz byla
> pouzita a pri sestavovani nove si toto testovat akorat by to mohlo byt
No to je prave to, cemu se chci vyhnout. Nepotrebuju vytvaret vsechny platne
kombinace, pouze potrebuju spocitat jejich pocet.
S pozdravem
Pavel Zichovsky (zichovsky@trul.cz)
Odpovedá: ivan.holubec@hella.com
15. 4. 2004 12:43
A nie je to pre tento pipad 12 / 4 = 3 ?
Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny (n=12), a
jedna
ctverice je (1,2,3,4), pak uz nesmi byt ctverice, kde by se vyskytovala
libovolna
dvojice z teto ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
Nedari se mi vymyslet postup, jak spocitat pocet platnych k-tic.
Dokazu spocitat pocet vsech moznych k-tic (jako kombinace k z n) ale uz
nevim, jak
spocitat pocet "neplatnych" k-tic (s "opakujicimi se" dvojicemi).
Odpovedá: Lukas Barton
15. 4. 2004 12:37
Ahoj,
=comb(n,k) * comb (n-k,k) * comb(n-2k,k) .... / ((n/k)!)
kde comb (a,b) je odpovidajici kombinacni cislo
Vyberu 1. k-tici, ze zbytku 2. k-tici a tak dal.K-tice vsak mohu
prohazovat, coz na rozdeleni do skupin nema vliv, proto to deleni.
Lukas
> Dobry den,
>
> neni to sice primo o programovani, ale potrebuju to pro program v Delphi.
>
> Trapim se uz nejakou dobu s timto problemem:
> Jako rychlou kontrolu splnitelnosti vstupnich podminek pro jeden program v
Delphi
> (rozlosovani turnaje) potrebuju spocitat pocet k-tic (bez ohledu na
poradi, k>2) z n-
> prvkove mnoziny (n>k) za nasledujici omezujici podminky:
> Libovolne dva prvky z mnoziny N muzou byt spolu maximalne v jedne k-tici.
>
> Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny (n=12), a
jedna
> ctverice je (1,2,3,4), pak uz nesmi byt ctverice, kde by se vyskytovala
libovolna
> dvojice z teto ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
>
> Nedari se mi vymyslet postup, jak spocitat pocet platnych k-tic.
> Dokazu spocitat pocet vsech moznych k-tic (jako kombinace k z n) ale uz
nevim, jak
> spocitat pocet "neplatnych" k-tic (s "opakujicimi se" dvojicemi).
>
> Nenasel by se nejaky matematik, ktery by mi s tim pomohl?
> Mohl bych si sice programove udelat vypis vsech moznych k-tic a pak
postupne
> "vyskrtavat" neplatne, ale se zvysujicim se poctem n a k by to trvalo
hrozne dlouho,
> takze kdyby to slo spocitat "vzoreckem", bylo by to jednodussi.
>
Odpovedá: Slavomir Skopalik
15. 4. 2004 12:46
Me se na tom neco nezda, jelikoz podle toho co ctu by pri
n=5 a k=4 byla jen jedna kombinace.
a to sice liovolna, ale jen jedna. Je to v poradku ?
Slavek
>
> Trapim se uz nejakou dobu s timto problemem:
> Jako rychlou kontrolu splnitelnosti vstupnich podminek pro
> jeden program v Delphi (rozlosovani turnaje) potrebuju
> spocitat pocet k-tic (bez ohledu na poradi, k>2) z n- prvkove
> mnoziny (n>k) za nasledujici omezujici podminky: Libovolne
> dva prvky z mnoziny N muzou byt spolu maximalne v jedne k-tici.
>
> Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny
> (n=12), a jedna ctverice je (1,2,3,4), pak uz nesmi byt
> ctverice, kde by se vyskytovala libovolna dvojice z teto
> ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
>
> Nedari se mi vymyslet postup, jak spocitat pocet platnych
> k-tic. Dokazu spocitat pocet vsech moznych k-tic (jako
> kombinace k z n) ale uz nevim, jak spocitat pocet
> "neplatnych" k-tic (s "opakujicimi se" dvojicemi).
Odpovedá: Frantisek Mlcoch
15. 4. 2004 12:59
Jde o kombinace bez opakovani. Vzorec jsem ti poslal na soukromy email.
F.
Odpovedá: Pavel Zichovsky
15. 4. 2004 12:56
Zdravim,
On 15 Apr 2004 at 13:13, ivan.holubec@hella.com wrote:
> A nie je to pre tento pipad 12 / 4 = 3 ?
>
> Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny (n=12), a
> jedna
Pro tento pripad (n=12. k=4) asi ano, ale bude to platit obecne pro jakekoliv
n>k>2?
To se obavam, ze ne... uz pro n=16 a k=4 mam vic vyhovujicich ctveric nez 4
(jen
tak zkusmo jich mam 9 a to urcite nebudou vsechny)....
S pozdravem
Pavel Zichovsky (zichovsky@trul.cz)
Odpovedá: Pavel Zichovsky
15. 4. 2004 13:01
Zdravim,
On 15 Apr 2004 at 13:25, Slavomir Skopalik wrote:
> Me se na tom neco nezda, jelikoz podle toho co ctu by pri
> n=5 a k=4 byla jen jedna kombinace.
> a to sice liovolna, ale jen jedna. Je to v poradku ?
Ano, to je naprosto v poradku, pri tomto zadani opravdu nemuzu sestavit vice
nez
jednu vyhovujici ctverici. Sice muze byt sestavena 5ti ruznymi zpusoby (to uz
pro
zadani neni podstatne), ale at ji sestavim jakkoliv, zadna dalsi uz podmince
vyhovovat nebude.
S pozdravem
Pavel Zichovsky (zichovsky@trul.cz)
Odpovedá: Jaromir Cermak
15. 4. 2004 13:13
Predpokladam n-prvkovou mnozinu a chci zni vybirat k prvkove podmnoziny, pak
pocet takovych podmnozin spocitam jako
n!/((n-k)!k!)
je to logicke. chci li spocitat kolika ruznych [poradi muzu vytvorit z n prvku
pouziju n! (n-faktorial), mne ale nezalezi na poslednich n-k prvcich a tak to
vydelim (n-k)! a nakonec, protoze mi nezalezi na poradi prvku staci to videlit
k!. Snad je to srozumitelne. Jinak to jde zapsat pro dvojice napr takto n.(n-
1)/2.
Jaromir Cermak
-----Original Message-----
From: Slavomir Skopalik [mailto:skopalik@elektlabs.cz]
> Trapim se uz nejakou dobu s timto problemem:
> Jako rychlou kontrolu splnitelnosti vstupnich podminek pro
> jeden program v Delphi (rozlosovani turnaje) potrebuju
> spocitat pocet k-tic (bez ohledu na poradi, k>2) z n- prvkove
> mnoziny (n>k) za nasledujici omezujici podminky: Libovolne
> dva prvky z mnoziny N muzou byt spolu maximalne v jedne k-tici.
>
> Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny
> (n=12), a jedna ctverice je (1,2,3,4), pak uz nesmi byt
> ctverice, kde by se vyskytovala libovolna dvojice z teto
> ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
>
> Nedari se mi vymyslet postup, jak spocitat pocet platnych
> k-tic. Dokazu spocitat pocet vsech moznych k-tic (jako
> kombinace k z n) ale uz nevim, jak spocitat pocet
> "neplatnych" k-tic (s "opakujicimi se" dvojicemi).
Odpovedá: Erik Salaj, Winsoft
15. 4. 2004 14:03
> =comb(n,k) * comb (n-k,k) * comb(n-2k,k) .... / ((n/k)!)
>
> kde comb (a,b) je odpovidajici kombinacni cislo
>
> Vyberu 1. k-tici, ze zbytku 2. k-tici a tak dal.K-tice vsak mohu
> prohazovat, coz na rozdeleni do skupin nema vliv, proto to deleni.
nezda sa mi to. Napr. pre k = 4, n >= 7 mas tam aj taku moznost (1, 2, 3, 4)
(1, 5, 6, 7)?
Pokial naozaj treba kontrolovat vstupne udaje na danu podmienku, tak sa
mi zda najjednoduchsie rovno ich kontrolovat, namiesto pocitania nejakych
kombinacii - ich spravny pocet mi predsa negarantuje, ze tie udaje su ok.
Erik
Odpovedá: martin kolos
15. 4. 2004 15:14
ahoj
ja jich nasel sest
napr:
1 2 3 4
2 5 6 7
6 8 9 10
10 11 12 1
3 5 8 11
4 7 9 12
martin kolos
>
>>> Tj. pokud vybiram napr. ctverice (k=4) z 12ti prvkove mnoziny
>>> (n=12), a jedna ctverice je (1,2,3,4), pak uz nesmi byt
>>> ctverice, kde by se vyskytovala libovolna dvojice z teto
>>> ctverice. Takze napr. (1,4,8,10) nebo (2,3,4,5) je spatne.
>
>>On 15 Apr 2004 at 13:13, ivan.holubec@hella.com wrote:
>> A nie je to pre tento pipad 12 / 4 = 3 ?
>>
>Pro tento pripad (n=12. k=4) asi ano, ale bude to platit obecne pro
>Pavel Zichovsky (zichovsky@trul.cz)
Odpovedá: Ing. Keder Vladimir
15. 4. 2004 19:34
Ahoj
Ak chces urobit rozlosovanie turnaja, skus sa pozriet na
http://avr-sr.host.sk/pravidla/sestkovy/Berger.html Jedna sa o bergerove
tabulky a podla tohoto kluca sa losuje futbalova liga. Na Slovesnku a iste
aj v Cechach to plati pre vsetky aj regionalne ligy na celu sezonu - jesenna
aj jarna cast.
Vlado
> neni to sice primo o programovani, ale potrebuju to pro program v Delphi.
>
> Trapim se uz nejakou dobu s timto problemem:
> Jako rychlou kontrolu splnitelnosti vstupnich podminek pro jeden program v
Delphi
> (rozlosovani turnaje) potrebuju spocitat pocet k-tic (bez ohledu na
poradi, k>2) z n-
> prvkove mnoziny (n>k) za nasledujici omezujici podminky: